Eliminating unused code, or dead code, from a computer program is an optimization technique performed by optimizing compilers. Dead code is essentially code within a computer program that provides a result that is never used. Because the result goes unused, the code producing the result may be eliminated from the program without any adverse effects to the execution of the program. In fact, eliminating dead code from a program may speed up the execution of the program and/or decrease the overall size of the program executable.
One common technique of eliminating dead code from a program involves utilizing an optimizing compiler to traverse a control flow graph of the program to identify and remove dead code. A control flow graph is a representation of the instruction flow of a computer program. A control flow graph models how the flow of a program proceeds from one instruction to the next along various edges, such as branches and calls. Unfortunately, traversing a control flow graph in control flow order to identify unused code is inefficient.
Because a control flow graph is structured to model the control flow of a program, traversing a control flow graph often involves visiting identical sections of code numerous times. For a program that may include many identical calls to one large routine (e.g., a routine containing numerous instructions), this can add substantial time to the overall optimization of the program. Further, because programs themselves often contain a large number of instructions, an optimization method that relies on eliminating dead code by traversing instructions of a control flow graph in control order can be very time intensive.